生成魔咒

Time Limit: 10 Sec Memory Limit: 128 MB

Description

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。

一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。

例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。

S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。

最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。

每次操作后都需要求出，当前的魔咒串 S 共有多少种生成魔咒。

Input

第一行一个整数 n。

第二行 n 个数，第 i 个数表示第 i 次操作加入的魔咒字符。

Output

输出 n 行，每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量

Sample Input

7
　1 2 3 3 3 1 2

Sample Output

1
　3
　6
　9
　12
　17
　22

HINT

1≤n≤100000

Main idea

询问在加入每一个字符后当前有多少个本质不同的子串。

Solution

直接用SAM，根据SAM的性质，每次增多的子串个数就是len[New] - len[fa[New]]。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 400005;
const int INF = 2147483640;

int n,x;
s64 Ans;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

struct SAM
{
    map <int, int> a[ONE];
    int len[ONE], fa[ONE];
    int last, cnt;
    SAM() {last = cnt = 1;}
    void Add(int c)
    {
        int x = last, New = last = ++cnt;
        len[New] = len[x] + 1;
        while(x && !a[x][c]) a[x][c] = New, x = fa[x];
        if(!x) {fa[New] = 1; Ans += len[New] - len[fa[New]]; return;}

        int q = a[x][c];
        if(len[x] + 1 == len[q]) fa[New] = q;
        else
        {
            int Nq = ++cnt;    len[Nq] = len[x] + 1;
            a[Nq] = a[q];
            fa[Nq] = fa[q];
            fa[New] = fa[q] = Nq;
            while(a[x][c] == q) a[x][c] = Nq, x = fa[x];
        }
        Ans += len[New] - len[fa[New]];
    }
}S;

int main()
{
    n = get();
    while(n--)
    {
        x = get();
        S.Add(x);
        printf("%lld\n", Ans);
    }

}